While the complexity of algorithms like polynomial multiplication is governed by the $O(n \cdot m)$ nature of the distributive property, the efficiency of basic list manipulation often hinges on the list's fundamental structure.
- The standard singly linked list restricts traversal to one direction, leading to $O(n)$ costs for operations that require access to the predecessor node (e.g., deletion without a predecessor pointer).
-
Doubly Linked List (DLL): The DLL extends the standard Node structure by adding a new pointer called prev. This pointer links the node to its immediate predecessor, enabling bidirectional traversal.
- Structure: $\{item, prev, next\}$.
- Benefit: Enables $O(1)$ deletion or insertion before a given node, assuming we already have a pointer to that node.
-
Circular Linked List (CLL): A CLL modifies the linkage pattern: the next pointer of the last node points back to the first node (head) of the list, forming a closed loop.
- Structure: Identical nodes to the standard list, but the list termination condition is changed (no NULL).
- Benefit: Allows the entire list to be traversed starting from any point. Simplifies managing circular buffers or queues.
Linked List Variant Comparison
| Property | Doubly Linked List | Circular Linked List |
|---|---|---|
| Structure | $\{item, prev, next\}$ | $\{item, next\}$ (Looping) |
| Traversal | Bidirectional | Start from any node |
| Deletion (Known Node) | $O(1)$ | $O(n)$ (Requires traversal to predecessor) |
| Termination | Head.prev = NULL, Tail.next = NULL | Tail.next points to Head |